Field of Invention
The invention relates to a method and controller for processing data multiplication in a RAID system and, in particular, to a method and controller for processing simultaneously a large amount of data multiplication operations in a RAID system.
Related Art
The redundant array of independent disk (RAID) is a disk subsystem designed to enhance access efficiency, to provide better fault-tolerance ability, or both. The RAID utilizes a disk striping technique to enhance the access efficiency. Data are stored separately according to bytes or groups of bytes in many different disk drives, so that the read/write I/O requests can be performed in parallel on many disk drives. On the other hand, a mirroring technique or a disk striping technique with distributive parity data is used to provide the fault-tolerance ability.
The ability of fault tolerance is related to the number of parity data sets stored in the RAID system. Taking RAID5 as an example, it is designed to store an extra set of parity data in addition to the user data. The parity data is usually called the P value, or sometimes the XOR parity because it is the calculation result of XOR operations on the corresponding user data. The formula is:P=D0+D1+D2+ . . . +Dn-1  (1)where + represents the XOR operation, P represents the parity data series, D0, D1, D2, . . . , Dn-1 represents the user data series, respectively, and n denotes the number of user data disks. As RAID5 only stores one parity data set, it can only allow one of the user data disks having errors (e.g. damaged or out of order) at a time. The data on the user data disk having errors is recovered using the corresponding P value and the corresponding data on the other normal user data disks by means of the same XOR operations. For example, if D1 has an error, then D1 can be recovered as follows:D1=D0+D2+ . . . +Dn-1+P                 where + also denotes the XOR operation.        
Considering the fault tolerance demand on more than one user data disk, some systems are designed to store multiple parities. “Reed-Solomon Codes” are usually adopted to set up this type of RAID systems, which allow more than one disk drive having errors. RAID6 belongs to this category. It has at least two parities to allow two or more disk drives having errors at the same time.
Take the RAID6 system with two parities as an example. The two parities are conventionally called P and Q. The formula for computing P is the same as the one in the RAID5 system. The value of Q is obtained using the following formula.Q=g0·D0+g1·D1+g2·D2+ . . . +gn-1·Dn-1  (2)
If two data disks Dx, Dy are damaged, then a careful derivation gives:Dx=A·(P+Pxy)+B·(Q+Qxy)  (3)Dy=(P+Pxy)+Dx  (4)                where A and B are constants only related to x and y:A=gy-x·(gy-x+1)−1  (5)B=g−x·(gy-x+1)−1  (6)        and Pxy and Qxy are the values of P and Q when both Dx and Dy are 0, i.e.,Pxy+Dx+Dy=P  (7)Qxy±gx·Dx+gy·Dy=Q  (8)        
Aside from the fact that the power “y−x” is a normal subtraction, the other algebraic operations in Eqs. (2) to (8) are all operations following the rules of the Galois Field. Moreover, g is a generator of the Galois Field. It usually be chosen as g=2.
The addition operation in the Galois Field is in fact the XOR operation. Its multiplication operation is related to the field of GF(2a). For the definitions, properties, and operational rules, please refer to (1) “The mathematics of RAID6”, H. Peter Anvin, December, 2004; and (2) “A Tutorial on Reed-Solomon Coding for Fault-Tolerance in RAID-like Systems”, James S. Plank, Software-Practice & Experience, 27(9), pp 995-1012, September, 1997. Eqs. (1) to (8) given above can be found in Ref. (1).
Since the Galois Field is a closed field and there always exists an r for an arbitrary number X satisfying X=2r, in the prior art looking up table is a typical method to deal with the multiplication operations in the Galois Field (see Ref. (2)). Take GF(2a) as an example. To find the product of any two numbers X and Y, the procedure is as follows:                1. Look up a log table to find r and s, which satisfies X=2r and Y=2s. Therefore, X·Y=2r+s=2t.        2. If t≧2a−1, then t=t−(2a−1).        3. Look up an inverse log table to obtain the value of 2t.        
It is seen from Eqs. (2) and (3) that a large amount of multiplication operations of Galois Field are required for computing Q or recovering the damaged Dx. In particular, it involves the multiplication of a constant with various different numbers. By means of the conventional method of looking up table, the system has to compute byte by byte and each multiplication operation of Galois Field requires 3 times of table looking up, 1 addition (or subtraction), 1 test and 1 modulo operation. Considering that the sizes of current storage media are frequently tens or hundreds of Giga bytes, such calculations are very inefficient and easy to become the bottleneck of the system. Therefore, how to improve and/or simplify and/or speed up the data multiplication operations in the RAID system is an important issue to be solved in the industry.